超时解法
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxResult = nums[0]
for i in range(len(nums)):
for o in range(i, len(nums) + 1):
if len(nums[i:o]) > 0 and sum(nums[i:o]) > maxResult:
maxResult = sum(nums[i:o])
return maxResult
动态规划:O(n) (手弟)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
retSum = nums[0]
mSum = 0
for num in nums:
if num + mSum < 0:
mSum = 0
if retSum < num:
retSum = num
else:
mSum += num
if retSum < mSum:
retSum = mSum
return retSum
动态规划:O(n) (andy)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
retSum = nums[0]
mSum = 0
for num in nums:
if mSum < 0:
mSum = num
else:
mSum += num
retSum = max(mSum, retSum)
return retSum